import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author wangj881
 * @date 2024-12-12 17:30
 */
public class L637_2 {

    public static void main(String[] args) {
        TreeNode treeNode3 = new TreeNode(15);
        TreeNode treeNode4 = new TreeNode(7);
        TreeNode treeNode1 = new TreeNode(2147483647);
        TreeNode treeNode2 = new TreeNode(2147483647);
        TreeNode treeNode = new TreeNode(2147483647, treeNode1, treeNode2);
        List<Double> doubles = new Solution().averageOfLevels(treeNode);
        System.out.println(doubles.toString());

    }

    static class Solution {
        public List<Double> averageOfLevels(TreeNode root) {
            List<Double> bl = new ArrayList<>();
            LinkedList<TreeNode> tmp = new LinkedList<>();
            tmp.add(root);
            long sum = 0;

            while (tmp.size() > 0) {
                int size = tmp.size();
                int sizeTmp = size;
                while (size > 0) {
                    TreeNode node = tmp.pollFirst();
                    sum += node.val;
                    if (node.left != null) {
                        tmp.addLast(node.left);
                    }
                    if (node.right != null) {
                        tmp.addLast(node.right);
                    }
                    size--;
                }
                bl.add((double)sum/sizeTmp);
                sum = 0;
            }
            return bl;
        }
    }
}
